#include<iostream>
#include<vector>
using namespace std;

/* 迭代算法 */

// 在R[i..n-1]中选择最小元素交换到R[i]位置
void Select(vector<int>& R, int i)
{
	// minj表示R[i..n-1]中最小元素的下标
	int minj = i;
	
	// 在R[i..n-1]中找最小元素
	for (int j=i+1; j<R.size(); j++)
		if (R[j] < R[minj])
			minj = j;
	
	// 若最小元素不是R[i]
	if (minj != i)
		swap(R[minj], R[i]);	 // 交换
}

// 迭代法：简单选择排序
void SelectSort1(vector<int>& R)	
{
	// 求向量长度
	int n=R.size();
	
	// 进行n-1趟排序
	for (int i=0; i<n-1; i++)
		Select(R, i);
}


/* 先递后合算法 */
void SelectSort21(vector<int>& R,int i)			// 递归的简单选择排序
{
	// 满足递归出口条件
	if (i==-1) return;
	
	SelectSort21(R, i-1);
	Select(R, i);
}

// 递归的简单选择排序
void SelectSort2(vector<int>& R)	
{
	SelectSort21(R, R.size()-2);
}

/* 先合后递算法 */
void SelectSort31(vector<int>& R,int i)			// 递归的简单选择排序
{
	int n=R.size();
	if (i==n-1) return;							// 满足递归出口条件
	Select(R, i);
	SelectSort31(R, i+1);
}

// 递归的简单选择排序
void SelectSort3(vector<int>& R)	
{
	SelectSort31(R, 0);
}

// 打印向量
void disp(vector<int>&a)
{
	for(int i=0; i<a.size(); i++)
		printf("%d ", a[i]);
	printf("\n");
}


int main()
{
	// 创建向量
	vector<int> a={2, 5, 4, 1, 3};
	
	// 打印向量
	printf("a: ");
	disp(a);
	
	// 选择排序
	SelectSort3(a);
	
	// 打印结果
	printf("排序\na: ");
	disp(a);
	return 0;
}
